/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 张宇田
 * Date: 2025-06-05
 * Time: 15:45
 */
import java.util.*;
//多项式类
class Polynomial {
    // 存储指数 -> 系数 的映射
    private final Map<Integer, Integer> terms = new HashMap<>();
    // key - value

    //构造函数 创建时使用下面的函数
    public Polynomial(String expression) {
        parse(expression);
    }

    //解析
    private void parse(String input) {
        input = input.replace(" ", "");       // 去除空格
        input = input.replaceAll("-", "+-");  // 统一变成 + 分割
        if (input.startsWith("+")) {
            input = input.substring(1);       // 去除多余的 +
        }

        String[] parts = input.split("\\+");
        for (String part : parts) {
            if (part.isEmpty()) continue;

            int coef = 0, exp = 0;

            if (part.contains("x")) {
                String[] temp = part.split("x");

                if (temp[0].isEmpty() || temp[0].equals("+")) {
                    coef = 1;
                } else if (temp[0].equals("-")) {
                    coef = -1;
                } else {
                    coef = Integer.parseInt(temp[0]);
                }

                if (temp.length > 1 && temp[1].startsWith("^")) {
                    exp = Integer.parseInt(temp[1].substring(1));
                } else {
                    exp = 1;
                }
            } else {
                coef = Integer.parseInt(part);
                exp = 0;
            }

            // ✅ 正确累加同类项
            terms.put(exp, terms.getOrDefault(exp, 0) + coef);
        }
    }

    //加法 输入另一个多项式
    public Polynomial add(Polynomial other) {
        //结果
        Polynomial result = new Polynomial("");
        for (Map.Entry<Integer, Integer> entry : this.terms.entrySet()) {
            result.terms.put(entry.getKey(), entry.getValue());
        }
        for (Map.Entry<Integer, Integer> entry : other.terms.entrySet()) {
            result.terms.put(entry.getKey(), result.terms.getOrDefault(entry.getKey(), 0) + entry.getValue());
        }
        return result;
    }
    //减法
    public Polynomial subtract(Polynomial other) {
        Polynomial result = new Polynomial("");
        for (Map.Entry<Integer, Integer> entry : this.terms.entrySet()) {
            result.terms.put(entry.getKey(), entry.getValue());
        }
        for (Map.Entry<Integer, Integer> entry : other.terms.entrySet()) {
            result.terms.put(entry.getKey(), result.terms.getOrDefault(entry.getKey(), 0) - entry.getValue());
            //result.terms.getOrDefault(entry.getKey() 去 result 里找相同指数的项；
        }
        return result;
    }
    //乘法
    public Polynomial multiply(Polynomial other) {
        Polynomial result = new Polynomial("");
        for (Map.Entry<Integer, Integer> term1 : this.terms.entrySet()) {
            for (Map.Entry<Integer, Integer> term2 : other.terms.entrySet()) {
                int newExp = term1.getKey() + term2.getKey();
                int newCoef = term1.getValue() * term2.getValue();
                result.terms.put(newExp, result.terms.getOrDefault(newExp, 0) + newCoef);
            }
        }
        return result;
    }

    @Override
    public String toString() {
        if (terms.isEmpty()) return "0";

        StringBuilder sb = new StringBuilder();
        List<Integer> exps = new ArrayList<>(terms.keySet());
        exps.sort(Collections.reverseOrder());

        for (int exp : exps) {
            int coef = terms.get(exp);
            if (coef == 0) continue;

            // 添加 "+" 符号（非首项且系数为正）
            if (sb.length() > 0 && coef > 0) sb.append("+");

            // 构造每一项
            if (exp == 0) {
                sb.append(coef);
            } else if (exp == 1) {
                if (coef == 1) sb.append("x");
                else if (coef == -1) sb.append("-x");
                else sb.append(coef).append("x");
            } else {
                if (coef == 1) sb.append("x^").append(exp);
                else if (coef == -1) sb.append("-x^").append(exp);
                else sb.append(coef).append("x^").append(exp);
            }
        }

        return sb.toString();
    }

}
